class Solution(object):
    def splitArray(self, nums):
        max_range = 100 + 1
        DP = [1] * max_range
        st = []
        min_prime = [1] * max_range
        for i in range(2, max_range):
            if DP[i] == 1:
                st.append(i)
                min_prime[i] = i
            for num in st:
                if i * num < max_range:
                    DP[i * num] = 0
                    min_prime[i * num] = num
                    if i % num == 0:
                        break
                else:
                    break
        f = [-1] * max_range
        last_min = 0
        for num in nums:
            now_min = float('inf')
            while num > 1:
                x = min_prime[num]
                num = num // x
                if f[x] == -1:
                    f[x] = last_min + 1
                else:
                    f[x] = min(f[x], last_min + 1)
                now_min = min(now_min, f[x])
            last_min = now_min
        return now_min


data = Solution()
nums = [6, 9]
print(data.splitArray(nums))
